1606E - Arena - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
signed main(){
    int n,x; cin >> n >> x;
    vector<vector<int>> p(x+1,vector<int> (n+1,0)),comb(n+1,vector<int> (n+1,0));
    for(int i=1;i<=x;i++){
        p[i][0] = 1;
        for(int j=1;j<=n;j++){
            p[i][j] = p[i][j-1]*i%mod;
        }
    }
    for(int i=0;i<=n;i++){
        comb[i][0] = 1;
        for(int j=1;j<=i;j++){
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j])%mod;
        }
    }
    vector<vector<int>> dp(n+1,vector<int> (x+1,0));
    for(int i=2;i<=n;i++){
        for(int j=1;j<=x;j++){
            if(j < i){
                dp[i][j] = (p[j][i] - p[j-1][i] + mod)%mod;
            }
            else{
                for(int k=0;k<=i;k++){
                    dp[i][j] = (dp[i][j] + dp[i-k][j-i+1]*p[i-1][k]%mod*comb[i][k]%mod)%mod;
                }
            }
        }
    }   
    int ans = 0;
    for(int i=1;i<=x;i++) ans = (ans + dp[n][i])%mod;
    cout << ans << '\n';
}